МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ Національний університет “Львівська політехніка” Інститут Комп’ютерних наук та інформаційних технологій Кафедра автоматизованих систем управління
Звіт до лабораторної роботи № 3 з курсу «Моделювання систем» на тему: «Імітаційне моделювання процесу функціонування скінченого дискретного стохастичного автомата»  Мета роботи: вивчити процес функціонування дискретного скінченого стохастичного автомата та знайти його ймовірностні характеристики за даними експерименту. Короткі теоретичні відомості У загальному випадку ймовірнісний автомат являє собою дискретний потактний перетворювач інформації з пам’яттю, функціонування якого в кожному такті залежить лише від стану пам’яті і може бути описаний статистично. Застосування схем ймовірнісних автоматів (Р-схем) має важливе значення для розвитку методів проектування дискретних систем, які виявляють статистично закономірну поведінку, обгрунтування алгоритмічних можливостей таких систем та доцільності їх використання, а також для розв’язування задач синтезу дискретних стохастичних систем за обраним критерієм з урахуванням обмежень. У загальному випадку ймовірнісний автомат являє собою дискретний потактний перетворювач інформації з пам’яттю, функціонування якого в кожному такті залежить лише від стану пам’яті і може бути описаний статистично. Застосування схем ймовірнісних автоматів (Р-схем) має важливе значення для розвитку методів проектування дискретних систем, які виявляють статистично закономірну поведінку, обгрунтування алгоритмічних можливостей таких систем та доцільності їх використання, а також для розв’язування задач синтезу дискретних стохастичних систем за обраним критерієм з урахуванням обмежень. Розглянемо більш загальну математичну схему. Нехай Ф - множина різноманітних пар виду
, де yj - елемент Y. Поставимо вимогу, щоб довільний елемент множини G спричиняв на множині Ф деякий закон розподілу: Елементи з Ф
(xi,zs) b11 b12 ... bk,j-1 bkj При цьому
, bkj - ймовірності переходу автомата в стан Zk та генераці вихідного сигналу yj, якщо він знаходився в стані Zs та на його вхід в цей момент прийшов сигнал xi. Число таких розподілів, які подаються у вигляді таблиць, дорівнює числу елементів множини G. Позначимо множину таких таблиць В і отримаємо опис стохастичного дискретного автомата в вигляді четвірки
. Окремий випадок Р-автомата
- це автомат, у якого перехід в новий стан або вихідний сигнал визначаються детерміновано. В першому випадку такий автомат називається Z-детермінованим стохастичним автоматом, в другому - Y-детермінованим. Розглянемо Y-детермінований P-автомат, який заданий таблицею переходів та виходів:
Таблиця переходів Y-детермірнованого Р-автомата Zk Zk   Z1 Z2 ... Zk-1 Zk  Z1 Z2 ... Zk p11 p21 ... pk1 p12 p22 ... pk2 ... ... ... ... p1(k-1) p2(k-1) ... pk(k-1) p1k p2k ... pkk   Таблицю переходів можна в цьому випадку представити у вигляді квадратної матриці перехідних ймовірностей Р:
. При цьому має виконуватися умова, що
. Для повного опису Y-детермінованого Р-автомата необхідно також визначити початковий розподіл ймовірностей виду
де dk - ймовірність того, що на початку роботи Р-автомат знаходиться в стані Zk. До початку функціонування Р-автомат знаходиться в стані Z0 і в нульовий такт часу змінює стан згідно з розподілом D. Подальший процес зміни станів автомата визначається матрицею переходів Р. Можливе також введення інформації про початковий стан в матрицю Р шляхом збільшення її розмірності на одиницю до
. Перший рядок цієї матриці відповідає початковому стану Z0 і має вигляд
, а перший стовпчик буде нульовим. З точки зору математичного апарату цей автомат еквівалентний дискретному марківському ланцюгу. Варіант 38 Z0 Z1 Z2 Z3 Z4 Z5  0 1 1 1 0 0    z0 z1 z2 ...